package Bi_Tree.symmetry_Bitree;

import Bi_Tree.TreeNode;


import java.util.*;

public class lc101 {

    public boolean isSymmetric1(TreeNode root) {
        /**
        * @Description: 递归法
        * @Param: [root]
        * @return: boolean
        * @Author: lsy
        * @Date: 2024/5/4 0004
        */
        return compare_isSymmetric1(root.left,root.right);
        }
        public boolean compare_isSymmetric1(TreeNode leftchild,TreeNode rightchild){
        /**
        * @Description:
         *
        * @Param: [leftchild, rightchild] 比较的是左右两个子树是否对称，因此传入的参数是节点的两个孩子
        * @return: boolean
        * @Author: lsy
        * @Date: 2024/5/4 0004
        */
        //终止条件
        if(leftchild==null&&rightchild==null){
            return true;
        } else if (leftchild!=null&&rightchild==null) {
            return false;
        } else if (leftchild==null&&rightchild!=null) {
            return false;
        } else if (leftchild.val!= rightchild.val) {
            return false;
        }
        //单层递归逻辑
            boolean outside = compare_isSymmetric1(leftchild.left, rightchild.right);   // 左子树：左、 右子树：右
            boolean inside = compare_isSymmetric1(leftchild.right, rightchild.left);    // 左子树：右、 右子树：左
            boolean isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
            return isSame;

        }


    public boolean isSymmetric2(TreeNode root) {
        /** 
        * @Description: 利用双向队列
        * @Param: [root]
        * @return: boolean
        * @Author: lsy
        * @Date: 2024/5/5 0005
        */
        
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            deque.offerFirst(leftNode.left);
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }


    }


